class Solution {
public:
    const static int mod = 1e9 + 7; 
    int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
                                        
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        vector<vector<vector<int> > > dp(maxMove+1,vector<vector<int>>(m,vector<int>(n,0)));
        dp[0][startRow][startColumn] = 1;
        int ret = 0;
        
        for(int k = 0;k < maxMove;k++){
            for(int i = 0;i < m;i++){
                for(int j = 0;j < n;j++){
                    int count = dp[k][i][j];
                    if(count > 0){
                        for(int d = 0;d < 4;d++){
                            int x = i + dir[d][0];
                            int y = j + dir[d][1];
                            if(x >= 0 && x < m && y >= 0 && y < n){
                                dp[k+1][x][y] = (dp[k+1][x][y] + count) % mod;
                            }else{
                                ret = (ret + count) % mod;
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }
};
